package m202405.d13;

/**
 * @@author: 爱做梦的锤子
 * @date: 2024/5/13 17:04
 */
public class Q124 {
    public int maxPathSum(TreeNode root) {
        travel(root);
        return max;
    }

    int max = Integer.MIN_VALUE;

    private int travel(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int l = Math.max(travel(node.left), 0);
        int r = Math.max(travel(node.right), 0);
        max = Math.max(l + r + node.val, max);
        return node.val + Math.max(l, r);
    }
}
